package com.yxp.offer;

import java.util.Stack;

/**
 * @author : yang.xp
 * @date : 2021/9/1 19:01
 * @description : 剑指 Offer 33. 二叉搜索树的后序遍历序列
 */
public class Problem33 {

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 6, 3, 2, 5};
        Problem33 problem33 = new Problem33();
        System.out.println(problem33.verifyPostorder(numbers));

    }

    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}
